/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        TreeNode* cur = root;
        while (cur)
        {
            if (cur->val > val)
            {
                cur = cur->left;




            }
            else if (cur->val < val)
            {
                cur = cur->right;
            }
            else
            {
                return cur;



            }








        }
        return nullptr;







    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* prev = nullptr;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
        bool left = isValidBST(root->left);
        if (prev != nullptr && prev->val >= root->val)
            return false;
        else
        {
            prev = root;
        }
        bool right = isValidBST(root->right);
        return left && right;
    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ret = INT_MAX;
    TreeNode* prev = nullptr;
    void getMin(TreeNode* root) {
        if (root == nullptr)
            return;
        getMin(root->left);
        if (prev != nullptr)
        {
            ret = min(ret, root->val - prev->val);
        }
        prev = root;
        getMin(root->right);

    }
    int getMinimumDifference(TreeNode* root) {

        getMin(root);
        return ret;








    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	TreeNode* deleteNode(TreeNode* root, int key) {
		TreeNode* find = root;
		if (root == nullptr)
			return nullptr;
		TreeNode* cur = root;
		TreeNode* parent = nullptr;
		while (cur)
		{

			if (cur->val > key)
			{
				parent = cur;
				cur = cur->left;



			}
			else if (cur->val < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				if (cur->left == nullptr)
				{
					if (cur == root)
					{
						root = cur->right;
						return root;



					}
					else
					{
						if (cur == parent->left)
						{
							parent->left = cur->right;

						}
						else
						{
							parent->right = cur->right;
						}

					}



					delete cur;

				}
				else if (cur->right == nullptr)
				{
					if (cur == root)
					{
						root = cur->left;
						return root;
					}
					else
					{
						if (cur == parent->left)
						{
							parent->left = cur->left;

						}
						else
						{
							parent->right = cur->left;
						}


					}


					delete cur;


				}
				else
				{
					TreeNode* leftmaxparent = cur;
					TreeNode* leftmax = cur->left;
					while (leftmax->right)
					{
						leftmaxparent = leftmax;
						leftmax = leftmax->right;

					}
					swap(cur->val, leftmax->val);
					if (leftmaxparent->right == leftmax)
						leftmaxparent->right = leftmax->left;
					else
						leftmaxparent->left = leftmax->left;
					delete leftmax;
				}

				return find;
			}






		}



		return find;






	}

};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	TreeNode* insertIntoBST(TreeNode* root, int val) {
		TreeNode* find = root;
		if (root == nullptr)
		{
			root = new TreeNode(val);
			return root;

		}
		TreeNode* cur = root;
		TreeNode* parent = nullptr;
		while (cur)
		{
			if (cur->val > val)
			{
				parent = cur;
				cur = cur->left;


			}
			else if (cur->val < val)
			{
				parent = cur;
				cur = cur->right;



			}
			else
			{

				return find;
			}







		}
		cur = new TreeNode(val);
		if (parent->val > val)
		{
			parent->left = cur;



		}
		else
		{

			parent->right = cur;


		}
		return find;




















	}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	TreeNode* sortbstree(vector<int>& nums, int left, int right) {
		if (left > right)
			return nullptr;


		int mid = (left + right) / 2;
		TreeNode* root = new TreeNode(nums[mid]);
		root->left = sortbstree(nums, left, mid - 1);
		root->right = sortbstree(nums, mid + 1, right);

		return root;
	}
	TreeNode* sortedArrayToBST(vector<int>& nums) {


		TreeNode* root = sortbstree(nums, 0, nums.size() - 1);
		return root;








	}
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	int prev = 0;
	TreeNode* convertBST(TreeNode* root) {


		if (root == nullptr)
			return nullptr;
		convertBST(root->right);
		root->val += prev;
		prev = root->val;
		convertBST(root->left);
		return root;

	}
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	int prev = 0;
	TreeNode* bstToGst(TreeNode* root) {
		if (root == nullptr)
			return nullptr;
		bstToGst(root->right);
		root->val += prev;
		prev = root->val;
		bstToGst(root->left);
		return root;
	}
};